HW 10

---

Question 1

• Brent’s Theorem: A result in computer science that provides an upper bound on the number of iterations required by an algorithm to find a repeating state in a sequence, given that the sequence is generated by a function that maps a set of states to itself.
• Bulk Synchronous Parallel (BSP) Model: A computation is divided into a set of tasks that are assigned to a group of processors. Each task can be executed independently, and each processor can work on multiple tasks simultaneously. At the end of each superstep, the processors synchronize by exchanging data and ensuring that all tasks have completed their computation phase.
• Sorting Network: A parallel algorithm that is used to sort a set of input values using a fixed set of comparison operations. In a sorting network, the input values are compared and swapped in a predetermined order until the values are sorted in ascending or descending order.
• Monotonic Sequence: A sequence of numbers that either increases or decreases consistently over time.
• Bitonic Sequence: A sequence of numbers that first increases and then decreases, or vice versa.
• Bitonic Merge: A type of parallel sorting algorithm that combines two sorted bitonic sequences into a single sorted bitonic sequence.
• Breadth First Search: A graph traversal algorithm that explores all the vertices of a graph or a tree in a breadth-first manner. It starts at the root or any arbitrary node, and explores all the neighboring nodes at the present depth level before moving on to the nodes at the next level.

Question 2

Part 1

Each layer has a total of $n/2$ comparators. In total, we have $\log n$ layers. Thus, we have a total of $n\log n$ comparisons.

Part 2

Each layer has $n/2$ more comparisons than the previous layer. Therefore, in total, we have $\sum_{i=1}^{\log n -1} n\cdot i / 2$

Question 3

// Initialization
for k = 0 to log2(n) - 1:
    for i = 0 to n - 1:
        for j = 0 to i - 1:
            // Perform bitonic merge on elements (i,j) and (i,n-1-j)
            if (i+j) mod 2 == 0:
                if element(i,j) > element(i,n-1-j):
                    swap(element(i,j), element(i,n-1-j))
            else:
                if element(i,j) < element(i,n-1-j):
                    swap(element(i,j), element(i,n-1-j))
                
// Bitonic Merge
for k = log2(n) - 2 downto 0:
    // Permute rows
    for i = 0 to n - 1:
        dest = (i + 2^k) mod n
        permute(row(i), row(dest))
    // Permute columns
    for j = 0 to n - 1:
        dest = (j + 2^k) mod n
        permute(column(j), column(dest))
    // Perform bitonic merge
    for i = 0 to n - 1:
        for j = 0 to i - 1:
            if (i+j) mod 2 == 0:
                if element(i,j) > element(i,n-1-j):
                    swap(element(i,j), element(i,n-1-j))
            else:
                if element(i,j) < element(i,n-1-j):
                    swap(element(i,j), element(i,n-1-j))

Question 4

Part 1

// Bitonic Merge algorithm
void bitonic_merge(int* A, int n) {
    if (n == 1) return;
    // Recursively make the two halves of A bitonic
    bitonic_merge(A, n/2);
    bitonic_merge(A + n/2, n/2);
    // Perform log2(n) stages of bitonic merging
    for (int k = 1; k <= log2(n); k++) {
        int d = pow(2, k-1);
        for (int j = n-1; j >= 0; j--) {
            int i = (j ^ d);
            if (i > j) {
                // Compare and swap elements at indices i and j
                if ((j & n) == 0 && A[j] > A[i]) {
                    swap(A[i], A[j]);
                }
                if ((j & n) != 0 && A[j] < A[i]) {
                    swap(A[i], A[j]);
                }
            }
        }
    }
}

Recurrence relation: $T(n) = 2T(n/2) + n \log n$

Using the master theorem, we can determine that the time complexity of the Bitonic Merge algorithm on a linear array is $O(n \log^2 n)$

Part 2

void bitonic_sort(int a[], int l, int r) {
    if (l < r) {
        int m = (l + r) / 2;
        bitonic_sort(a, l, m);
        bitonic_sort(a, m+1, r);
        bitonic_merge(a, l, r);
    }
}

Recurrence relation: $T(n) = 2T(n/2) + n\log n$

Using the Master Theorem, the solution to the above recurrence relation is:

$T(n) = O(n \log^2n)$